查看原文
其他

大话系列 | SVM(上)—听说你喜欢挑战难的

小一 小一的学习笔记 2023-01-01
关注+星标,听说他有点东西
全文共2786字,阅读全文需16分钟



写在前面的话

大家好,我是小一

摊牌了,摊牌了,竟然有人说前几篇算法都太简单了,分分钟搞定,那你可真是后生可畏

今天开始说SVM,一种略显复杂但分类效果很不错的分类算法。相比而言会略优于前几种算法,而且在实际项目中也比较常用,就是理解起来有点费头发


准备好了吗?



1. 支持向量机理论

支持向量机(Support Vector Machine:SVM)

支持向量机的目的是什么?

利用训练数据集的间隔最大化找到一个最优分离超平面

你可能有两个名词不太懂,间隔?分离超平面?别紧张,没有人刚开始学习SVM的时候就知道这两个东西


先来看个例子,现在有一些人的身高和体重数据,将它们绘制成散点图,是这样的:

如果现在给你一个未知男女的身高和体重,你能分辨出性别吗?

这个简单,我直接将已知的点划分为两部分,这个点落在哪一部分就对应相应的性别

ok,那就可以画一条直线,直线以上是男生,直线以下是女生

问题来了,现在这个是一个二维平面,我们可以画直线,如果是三维的呢?该怎么画?

小时候就学过,一维平面是点,二维平面是线,三维平面是面

对的,那么注意,今天的第一个概念:

超平面是平面的一般化:

  • 在一维的平面中,它是点
  • 在二维的平面中,它是线
  • 在三维的平面中,它是面
  • 在更高的维度中,我们称之为超平面

为了大家更快的适应超平面这种说法,后面的直线、平面都直接叫超平面了

继续刚才的问题,我们刚才是通过一个分离超平面分出了男和女,这个超平面唯一吗?

很明显,并不唯一,这样的超平面有若干个

那么问题来了,既然有若干个,那我肯定要最好的,这里最好的叫最优分离超平面

如何在众多分离超平面中选择一个最优分离超平面?

下面这两个分离超平面,你选哪个?绿色的还是黑色的?

对,当然是黑色的。

黑色的我懂,可是原理是什么?

很简单,原理有两个,分别是:

  • 正确的对训练数据进行分类
  • 对未知数据也能很好的分类

黑色的分离超平面能够对训练数据很好的分类,当新增未知数据时,黑色的分离超平面泛化能力也强于绿色。

深究一下,为什么黑色的要强于绿色?原理又是什么?

其实很简单:最优分离超平面其实是和两侧样本点有关,而且只和这些点有关。

怎么理解这句话呢,我们看张图:

其中当间隔达到最大,两侧样本点的距离相等的超平面为最优分离超平面。

注意,今天的第二个概念:

对应上图,Margin对应的就是最优分离超平面的间隔,此时的间隔达到最大

一般来说,间隔中间是无点区域,里面不会有任何点(理想状态下)

给定一个超平面,我们可以就算出这个超平面与和它最接近的数据点之间的距离。那么间隔(Margin)就是二倍的这个距离

我还是不理解为什么这个分离超平面就是最优分离超平面

那你在看这张图

在这张图里面间隔MarginB小于上张图的MarginA

当出现新的未知点,MarginB分离超平面的泛化能力不如Margin

你可能不理解泛化能力这个词,那换个说法:当出现未知点时,用MarginB的分离超平面去分类,错误率大于MarginA



总结一下

支持向量机是为了通过间隔最大化找到一个最优分离超平面

而之所以叫做支持向量,是因为在决定分离超平面的时候,只有极限位置的那两个点有用,其他点根本没有大作用,因为只要极限位置离得超平面的距离最大,就是最优的分离超平面了。


怎么样,一口气学了这么多,甚至还了解了SVM的深奥意义,是不是有点点小激动?

趁着现在还激动想一个问题:如何确定最大化间隔?


2. 如何确定最大化间隔

如果我们能够确定两个平行超平面,那么两个超平面之间的最大距离就是最大化间隔。

看个图你就都明白了:

左右两个平行超平面将数据完美的分开,我们只需要计算上述两个平行超平面的距离即可。

所以,我们找到最大化间隔:

  • 找到两个平行超平面,可以划分数据集并且两平面之间没有数据点
  • 最大化上述两个超平面

2.1. 确定两个平行超平面

怎么确定两个平行超平面?

我们知道一条直线的数学方程是:y-ax+b=0,而超平面会被定义成类似的形式:

超平面的方程中,加粗的字体w、x表示向量,表示向量的内积。

这个我觉得应该不用多说了,平面方程公式,默认都懂哈

推广到n维空间,则超平面方程中的w、x分别为:

等等,还有一个问题,如何确保两超平面之间没有数据点?

我们的目的是通过两个平行超平面对数据进行分类,那我们可以这样定义两个超平面:

对于每一个向量xi:满足:

或者

也就是这张图:

所有的红点都是1类,所有的蓝点都是−1类。

整理一下上面的两个超平面:

不等式两边同时乘以 yi,-1类的超平面yi=-1,要改变不等式符号,合并后得

ok,记住上面的约束条件。


2.2. 确定间隔

如何求两个平行超平面的间隔呢?

我们可以先做这样一个假设:

  • 是满足约束的超平面
  • 是满足约束的超平面
  • 上的一点

则x0到平面h1的垂直距离m就是我们要的间隔。

这个间隔是可以通过计算算出来的,推导还需要一些步骤,直接放结果了就:

其中||w||表示w的二范数,求所有元素的平方和,然后在开方。比如,二维平面下:

可以发现,w 的模越小,间隔m 越大


2.3. 确定目标

我们的间隔最大化,最后就成了这样一个问题:

使

了其中w和b,我们的最优分离超平面就确定了,目的也就达到了


上面的最优超平面问题是一个凸优化问题,可以转换成了拉格朗日的对偶问题,判断是否满足KKT条件,然后求解

上一句话包含的知识是整个SVM的核心,涉及到大量的公式推导。

但是既然是大话系列,那么涉及到推导的东西我们就略过了,你只需要知道它的目的就是为了找出一个最优分离超平面

就假设我们已经解出了最大间隔,找到了最优分离超平面,它是这样的:


ok,那我们的支持向量机的原理就说完了。

除去上面我们对最大间隔的推导计算,剩下的部分其实是不难理解的。

从上面过程,我们可以发现,其实最终分类超平面的确定依赖于部分极限位置的样本点,这叫做支持向量。

由于支持向量在确定分离超平面中起着决定性作用,所有将这类模型叫做支持向量机

留个问题

我们在上面图中的点都是线性可分的,也就是一条线(或一个超平面)可以很容易的分开的

但是实际情况不都是这样,比如有的女生身高比男生高,有的男生体重比女生都轻

像这种存在噪声点分类,应该怎么处理?

思考一下,下节接着说



写在后面的话

一直在想怎么把SVM说的清楚些,毕竟算是一个机器学习领域比较重要的算法

直到文章得到小组其他小伙伴的认可,回过头在看文章,突然觉得本来就挺好,不需要在润色啥的,然后就发出来了

当然文章内容比较多,就分成了几部分,理解起来会容易些

学算法嘛,别给自己太大压力,理解差不多了就搞个项目练一练,这也是小一最初的想法,希望能对大家有点用处。

另外,机器学习系列文章都在文章开头的专辑中,你可以收藏起来方便阅读



往期推荐

大话系列 | 决策树(上篇)—理论

大话系列 | 决策树(中篇)—理论

大话系列 | 决策树(下篇)—实战

大话系列 | 贝叶斯(上篇)—理论

大话系列 | 贝叶斯(下篇)—实战

大话系列 | k近邻(上篇)—理论

大话系列 | k近邻(中篇)—KD树

大话系列 | k近邻(下篇)—实战







好巧啊,你也读到这了!    

点个在看让小一看到你

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存